public class No008 {
    /**
     * 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。
     * 注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
     */
    public static class TreeLinkNode {
        String val;
        TreeLinkNode left = null;
        TreeLinkNode right = null;
        TreeLinkNode next = null;

        @Override
        public String toString() {
            return "TreeLinkNode{" +
                    "val='" + val + '\'' +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }

        TreeLinkNode(String val) {
            this.val = val;
        }

    }

    public static TreeLinkNode GetNext(TreeLinkNode pNode) {
        // 1. 有右孩子，找右孩子的最左孩子
        if (pNode.right != null) {
            TreeLinkNode pRight = pNode.right;
            while (pRight.left != null) {
                pRight = pRight.left;
            }
            return pRight;
        }
        // 2. 是父亲的左孩子
        if (pNode.next != null && pNode.next.left == pNode) {
            return pNode.next;
        }
        // 3. 是父亲的右孩子
        if (pNode.next != null) {
            TreeLinkNode pNext = pNode.next;
            while (pNext.next != null && pNext.next.right == pNext) {
                pNext = pNext.next;
            }
            return pNext.next;
        }
        // 4. 是最后一个节点
        return null;
    }

    public static void main(String[] args) {
        TreeLinkNode A = new TreeLinkNode("A");
        TreeLinkNode B = new TreeLinkNode("B");
        TreeLinkNode C = new TreeLinkNode("C");
        TreeLinkNode D = new TreeLinkNode("D");
        TreeLinkNode E = new TreeLinkNode("E");
        TreeLinkNode F = new TreeLinkNode("F");
        TreeLinkNode G = new TreeLinkNode("G");
        TreeLinkNode H = new TreeLinkNode("H");
        TreeLinkNode I = new TreeLinkNode("I");
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        B.next = A;
        C.left = F;
        C.right = G;
        C.next = A;
        D.next = B;
        E.left = H;
        E.right = I;
        E.next = B;
        F.next = C;
        G.next = C;
        H.next = E;
        I.next = E;
        System.out.println(A);
        System.out.println(GetNext(B).val);
    }
}
